package middle;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.Set;

/**
 * 无重复字符的最长子串
 * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
 * 链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class LongestSubstringWithoutRepeatingCharacters {
    public static void main(String[] args) {
        Solution2 solution = new Solution2();
        solution.lengthOfLongestSubstring("pwwkew");
    }
    /**
     * 重复这两个字 很容易让人联想到Hash表。
     * 所以很快我就有了一个思路。
     * 循环一次该字符串，用size来记录不重复的字符数量，每次将字符放入到哈希表中，如果出现相同的，则表示重复，
     * 这时候，将size跟上次的size比较，如果大于上一次，就给上次的size更新为最新的（默认为0）。
     *
     * 但是有一个问题，哈希表只能保存一次啊。第一次遇到重复的数据以后，第二次肯定是重新开始计算size了，也就是必须得清空哈希表，一切从头开始了。
     * 比如使用HashMap，java提供了clear方法用来清空它。
     * 还有其他更好的办法吗?
     *
     * 我们来观察一组数 abcecfda
     * 很明显 这组数没有重复数据最长的子字符串是ecfda.我们最开始从第一个字母a开始取数。
     * 一直取，直到遇到了第二个c，这时候数组里面有abce是不重复的 size=4；
     * 我们第二次开始应当从重复字符(即c)的后一位e开始。在e之前的abc在重新开始的子字符串都不能算作重复了。
     * ok，其实我们就已经找到了临界线。我们用一个变量start来记录这个临界线，表示新的字符串开始的位置。
     * */
    static class Solution {
        public int lengthOfLongestSubstring(String s) {
            HashMap<Character, Integer> hashMap = new HashMap<>();
            int start = 0;
            int size = 0;
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                // 已经存在的情况
                if(hashMap.containsKey(c) && hashMap.get(c) >= start){
                    start = hashMap.get(c)+1;
                }
                // ??? 为什么size放在这里 为什么 +1 ??
                size = Math.max(i-start+1,size);
                hashMap.put(c,i);
            }
            return size;
        }
    }


    /**
     * 用while循环 一样的思路
     * */
    static class Solution1 {
        public int lengthOfLongestSubstring(String s) {
            int ans = 0;
            HashMap<Character, Integer> map = new HashMap<>();
            int left = 0;
            int right = 0;
            while (right < s.length()) {
                char c = s.charAt(right);
                if (map.containsKey(c) && map.get(c) >= left) {
                    left = map.get(c) + 1;
                }
                // 细节 : 为什么ans放在这里赋值 为什么 +1 ??
                ans = Math.max(ans, right - left);
                map.put(c, right++);
            }
            return ans;
        }
    }

    /**
     * 滑动窗口
     * 每个字符都作为一次起点，这样我们就不需要使用HashMap来记录索引了，而改用Set来记录重复
     * 然后使用一个r指针 往右移动，当遇到set中存在的元素时，就记录一下长度
     * */
    static class Solution2 {
        public int lengthOfLongestSubstring(String s) {
            int ans = 0;
            // 这里为什么初始化为-1， 这样的话，保证能参与一次while循环
            int r = -1;
            Set<Character> set = new HashSet<>();
            for (int i = 0; i < s.length(); i++) {
                if (i != 0) {
                    // 左移并移除上一个
                    set.remove(s.charAt(i-1));
                }
                // 细节，为什么这里用 r + 1来做条件。 因为ans的计算，可以演示一遍
                while (r + 1 < s.length() && !set.contains(s.charAt(r + 1))) {
                    set.add(s.charAt(r + 1));
                    r++;
                }
                ans = Math.max(ans, r - i + 1);
            }
            return ans;
        }
    }
}
